package cn.dlc.com.sort;

import java.util.Arrays;

/**
 * @author 邓立川
 * @date 2021/3/14 10:27
 * @desc 希尔排序 {9,1,2,5,7,4,8,6,3,5}
 */
public class Demo11 {

    public static void main(String[] args) {
        Integer[] arr = {9,1,2,5,7,4,8,6,3,5};
        HillSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void HillSort(Comparable[] arr){

        // 确定h的初始值
        int h = 1;
        while(h < arr.length / 2) {
            h = 2*h + 1;
        }

        // 希尔排序
        while(h >=1) {

            // 依次获取改组中被比较的元素，比如h为5，那么获取第6个元素
            // 其实就是这个组中的第二个元素
            for(int i = h ; i < arr.length; i++) {
                // 获取待比较的元素（当前组的排序好的），注意这j的变化
                // 注意截止的条件，为h，表示的是当前组的排好序
                // 的那部分的第二个元素，因为还要-h
                for(int j = i ; j >= h; j-=h ) {
                    // j-h表示当前组的前一个元素，因为跨度为h
                    if(SortUtils.greater(arr[j-h],arr[j])) {
                        // 排序好的比没有排序的大，交换
                        SortUtils.exchange(arr,j-h,j);
                    } else {
                        // 没有找到，比如上面的10,12
                        break;
                    }
                }
            }
            // 重置h的值
            h = h / 2;
        }
    }
}
